|
The Fisher–Yates shuffle (named after Ronald Fisher and Frank Yates), also known as the Knuth shuffle (after Donald Knuth), is an algorithm for generating a random permutation of a finite set—in plain terms, for randomly shuffling the set. A variant of the Fisher–Yates shuffle, known as Sattolo's algorithm, may be used to generate random cyclic permutations of length ''n'' instead. The Fisher–Yates shuffle is unbiased, so that every permutation is equally likely. The modern version of the algorithm is also rather efficient, requiring only time proportional to the number of items being shuffled and no additional storage space. Fisher–Yates shuffling is similar to randomly picking numbered tickets (combinatorics: distinguishable objects) out of a hat without replacement until there are none left. == Fisher and Yates' original method == The Fisher–Yates shuffle, in its original form, was described in 1938 by Ronald Fisher and Frank Yates in their book ''Statistical tables for biological, agricultural and medical research''.〔 Note: the 6th edition, ISBN 0-02-844720-4, is (available on the web ), but gives a different shuffling algorithm by C. R. Rao. 〕 Their description of the algorithm used pencil and paper; a table of random numbers provided the randomness. The basic method given for generating a random permutation of the numbers 1 through ''N'' goes as follows: # Write down the numbers from 1 through ''N''. # Pick a random number ''k'' between one and the number of unstruck numbers remaining (inclusive). # Counting from the low end, strike out the ''k''th number not yet struck out, and write it down elsewhere. # Repeat from step 2 until all the numbers have been struck out. # The sequence of numbers written down in step 3 is now a random permutation of the original numbers. Provided that the random numbers picked in step 2 above are truly random and unbiased, so will the resulting permutation be. Fisher and Yates took care to describe how to obtain such random numbers in any desired range from the supplied tables in a manner which avoids any bias. They also suggested the possibility of using a simpler method — picking random numbers from one to ''N'' and discarding any duplicates—to generate the first half of the permutation, and only applying the more complex algorithm to the remaining half, where picking a duplicate number would otherwise become frustratingly common. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fisher–Yates shuffle」の詳細全文を読む スポンサード リンク
|